package com.hdu.other.dp.pakegeGroup;


import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

/**
 * <a href="https://www.luogu.com.cn/problem/P1757">分组背包模板</a>
 */
public class Template {

    private static final int MAX_N = 1001;
    private static int m, n;

    private static final int[][] ARR = new int[MAX_N][3];

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new java.io.InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
        StreamTokenizer st = new StreamTokenizer(reader);

        while (st.nextToken() != StreamTokenizer.TT_EOF) {
            m = (int) st.nval;
            st.nextToken();
            n = (int) st.nval;
            for (int i = 0; i < n; i++) {
                st.nextToken();
                ARR[i][0] = (int) st.nval;
                st.nextToken();
                ARR[i][1] = (int) st.nval;
                st.nextToken();
                ARR[i][2] = (int) st.nval;
            }
            Arrays.sort(
                    ARR,
                    0,
                    n,
                    Comparator.comparingInt(a -> a[2])
            );
            writer.println(cal());
        }
        writer.flush();
        reader.close();
        writer.close();
    }

    static int cal() {
        int groupSize = 1;
        for (int i = 1; i < n; i++) {
            if (ARR[i][2] != ARR[i - 1][2]) {
                groupSize++;
            }
        }
        int[][] dp = new int[groupSize + 1][m + 1];
        int groupIndex = 1;
        int start = 0;
        while (start < n) {
            int end = start + 1;
            while (end < n && ARR[end][2] == ARR[start][2]) {
                end++;
            }
            for (int j = 0; j <= m; j++) {
                dp[groupIndex][j] = dp[groupIndex - 1][j];
                for (int k = start; k < end; k++) {
                    if (j >= ARR[k][0]) {
                        dp[groupIndex][j] = Math.max(dp[groupIndex][j], dp[groupIndex - 1][j - ARR[k][0]] + ARR[k][1]);
                    }
                }
            }
            start = end;
            groupIndex++;
        }
        return dp[groupSize][m];
    }
}
